#include <iostream>
using namespace std;

#define MaxSize 10
/// @brief 顺序栈的定义
typedef struct
{
    char data[MaxSize]; // 静态数组存放栈中元素
    int top;            // 栈顶指针
} SqStack;

/// @brief 初始化栈
/// @param S
void InitStack(SqStack &S)
{
    S.top = -1; // 初始化栈顶指针
}

/// @brief 判断栈空
/// @param S
/// @return
bool StackEmpty(SqStack S)
{
    if (S.top == -1)
    {
        return true; // 栈空
    }
    else
    {
        return false; // 不空
    }
}

/// @brief 新元素入栈
/// @param S
/// @param x
/// @return
bool Push(SqStack &S, char x)
{
    if (S.top == MaxSize - 1)
    { // 栈满，报错
        return false;
    }
    S.top = S.top + 1;   // 指针先加一
    S.data[S.top] = x;   // 新元素进栈
    S.data[++S.top] = x; // 与上两行代码等价
    return true;
}

// 初战操作
bool Pop(SqStack &S, char &x)
{
    if (S.top == -1)
    { // 栈空，报错
        return false;
    }
    x = S.data[S.top]; // 栈顶元素先出栈
    S.top = S.top - 1; // 指针再减1
    return true;
}

/// @brief 读取栈顶元素
/// @param S
/// @param x
/// @return
bool GetTop(SqStack S, char &x)
{
    if (S.top == -1)
    { // 栈空报错
        return false;
    }
    x = S.data[S.top]; // x记录栈顶元素
    return true;
}

/// @brief 算法实现栈在括号匹配中的算法
/// @param str
/// @param length
/// @return
bool bracketCheck(char str[], int length)
{
    SqStack S;
    InitStack(S); // 初始化一个栈
    for (int i = 0; i < length; i++)
    {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{')
        {
            Push(S, str[i]); // 扫描到左括号，入栈
        }
        else
        {
            if (StackEmpty(S))
            {                 // 扫描到右括号，切当前栈空
                return false; // 匹配失败
            }
            char topElem;
            Pop(S, topElem); // 栈顶元素出栈
            if (str[i] == ')' && topElem != '(')
            {
                return false;
            }
            if (str[i] == ']' && topElem != '[')
            {
                return false;
            }
            if (str[i] == '}' && topElem != '{')
            {
                return false;
            }
        }
    }
    return StackEmpty(S); // 检索完全部括号后，栈空说明匹配成功
}